home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group02b.txt / 000076_icon-group-sender_Fri Oct 18 17:05:53 2002.msg < prev    next >
Internet Message Format  |  2003-01-02  |  2KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.11.1/8.11.1) id g9J05ec29243
  4.     for icon-group-addresses; Fri, 18 Oct 2002 17:05:40 -0700 (MST)
  5. Message-Id: <200210190005.g9J05ec29243@baskerville.CS.Arizona.EDU>
  6. Date: Fri, 18 Oct 2002 14:22:33 -0700
  7. From: Steve Wampler <swampler@noao.edu>
  8. X-Accept-Language: en
  9. To: "Boulet, Dan" <BouleDa@navcanada.ca>
  10. CC: "IconGroup (E-mail)" <icon-group@cs.arizona.edu>,
  11.    "Unicon Group (E-mail)" <unicon-group@lists.sourceforge.net>
  12. Subject: Re: [Unicon-group] recursive generators
  13. Errors-To: icon-group-errors@cs.arizona.edu
  14. Status: RO
  15.  
  16. "Boulet, Dan" wrote:
  17. ---------------------------------------------------------------------------
  18. This is an appeal to all experts in recursive generation.  Given the
  19. following string:
  20.  
  21. astring :=
  22. "[main],a,b,c,d,[a],a1,[b],b1,b2,[c],c1,c2,c3,[d],1,2,3,[a1],a11,a12,a13,[b1
  23. ],b11,b12,b13,b14,[b2],b21,b22,b23,b24,[a11],x,y,z"
  24.  
  25. Does anyone have any ideas on how the following sub-strings can be
  26. generated:
  27.  
  28. main,a,a1,a11,x
  29. main,a,a1,a11,y
  30. main,a,a1,a11,z
  31. main,a,a1,a12
  32. main,a,a1,a13
  33. main,b,b1,b11
  34. main,b,b1,b12
  35. main,b,b1,b13
  36. main,b,b1,b14
  37. main,b,b2,b21
  38. main,b,b2,b22
  39. main,b,b2,b23
  40. main,b,b2,b24
  41. main,c,c1
  42. main,c,c2
  43. main,c,c3
  44. main,d,1
  45. main,d,2
  46. main,d,3
  47. -----------------------------------------------------------
  48.  
  49. Well, first a question - do you intend such strings to represent
  50. just acyclic graphs or general graphs?  (Affects the answer slightly.)
  51.  
  52. I don't know if this is what you're looking for, but I'd approach
  53. the problem as a graph traversal problem.  First parse the string
  54. to build the graph and then generate all (acyclic) paths in the
  55. graph starting at the root node (presumably, that's the first node
  56. in the string, right?)
  57.  
  58.  
  59.  
  60.  
  61.  
  62.  
  63. -- 
  64. Steve Wampler -- swampler@noao.edu
  65. Quantum materiae materietur marmota monax si marmota
  66.                     monax materiam possit materiari?
  67.